【题解】跳楼机同余最短路 luogu3403

对于 $x,y,z$ 三个操作，我们先考虑 $y,z$ 两个操作的情况。

$f[i]$ 表示通过 $y,z$ 两个操作可以到达的 $mod x=i$ 最小的楼层。

可以得知：$f[i+y]=f[i]+y,f[i+z]=f[i]+z.$

对于最短路，我们可以用一下形式建边：

1	add(i,(i+y)%x,y); add(i,(i+z)%x,z);

没问题吧？%x是必须要做的操作，上文讲了。

那如何统计答案呢？

首先，如果这个 “最小的楼层” 超出了 $H$ ，那么显然是不用统计的。否则，我们将这样统计：ans+=(H-f[i])/x+1;

为什么要这样写呢？想想，现在我们知道了这个最小楼层，我们可以到达这个最小楼层，对吧？如果现在以这个最小楼层为起点，我们可以选择在往上跳 $x$ 层，或者是 $2x$ 层….知道 $nx$ 层，$(n+1)x$就会超出 $H$，这时上面的式子就好理解多了。

Code:(可以不用堆优$Dijstra$，没必要，用 $Spfa$ 就行了)

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
using namespace std;
const int N=1e5+3;
ll H,x,y,z,ans,f[N];
int vis[N],head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1]; 
inline void add(int x,int y,int v)
{G[++cnt].nxt=head[x],G[cnt].to=y,G[cnt].val=v,head[x]=cnt;}
inline void spfa(){
    memset(f,127,sizeof(f));
    queue<int> q;f[1]=1,vis[1]=1,q.push(1);
    while(q.size()){
        int x=q.front();q.pop();vis[x]=0;
		for(RI i=head[x];i;i=G[i].nxt){
		    if(f[G[i].to]>f[x]+G[i].val){
		        f[G[i].to]=f[x]+G[i].val;
				if(!vis[G[i].to])q.push(G[i].to),vis[G[i].to]=1;    
		    }
		} 
    }return;
}
int main(){
    scanf("%lld%lld%lld%lld",&H,&x,&y,&z);
    if(x==1||y==1||z==1){printf("%lld\n",H);return 0;}
    for(int i=0;i<x;++i){add(i,(i+y)%x,y);add(i,(i+z)%x,z);} 
    spfa();
    for(int i=0;i<x;++i)
	   if(f[i]<=H)ans+=(H-f[i])/x+1;
	printf("%lld\n",ans); 
    return 0;
}

本文标题:【题解】跳楼机同余最短路 luogu3403

文章作者:Qiuly

发布时间:2019年02月15日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/15/[题解]luoguP3403/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。

Code:(可以不用 堆优$Dijstra$，没必要，用 $Spfa$ 就行了)

Code:(可以不用堆优$Dijstra$，没必要，用 $Spfa$ 就行了)